package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


//40. 组合总和 II
//
//给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
//candidates 中的每个数字在每个组合中只能使用一次。
//
//说明：
//
//所有数字（包括目标数）都是正整数。
//解集不能包含重复的组合。 
//示例 1:
//
//输入: candidates = [10,1,2,7,6,1,5], target = 8,
//所求解集为:
//[
//  [1, 7],
//  [1, 2, 5],
//  [2, 6],
//  [1, 1, 6]
//]
//示例 2:
//
//输入: candidates = [2,5,2,1,2], target = 5,
//所求解集为:
//[
//  [1,2,2],
//  [5]
//]



public class Solution040 {
	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
        	return res;
        }
        
        Arrays.sort(candidates);
        
        dfs(candidates, target, res, new ArrayList<>(), 0, 0);
        return res;
    }
	
	
	
	private void dfs(int[] candidates, int target, List<List<Integer>> res, List<Integer> path, int sum, int start) {
		if (sum > target) {
			return;
		} else if (sum == target) {
			res.add(new ArrayList<>(path));
			return;
		}
		
		for (int i=start; i<candidates.length; i++) {
			
			if (i > start && candidates[i] == candidates[i-1]) {
				continue;
			}
			path.add(candidates[i]);
			dfs(candidates, target, res, path, sum + candidates[i], i+1);
			path.remove(path.size()-1);
		}
		
	}
}
